package ljl.alg.wangzheng_camp.round1.bisection;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
import java.util.stream.Collectors;

/**
 * 果然和我想的不太一样
 * 方法1 直接排序后 sublist
 * 方法2 双指针，他说，
 *
 * 我是不服的，我自己试试我的解法
 * 1. 找到它
 * 2. 没找到，找到比它小的和比它大的
 * 麻烦啊，感觉做不出来，还是排序省事！
 * 而且我这个思路应该是错的，放弃。
 *
 * */
public class _658_find_closest_k {
    
    public List<Integer> findClosestElements(int[] arr, int k, int x) {
        List<Integer> all = new ArrayList<>(arr.length);
        for (int each : arr) all.add(each);
        all.sort((a, b) -> {
            return a == b ? 0 : Math.abs(a - x) - Math.abs(b - x);
        });
        List<Integer> res = all.subList(0, k);
        Collections.sort(res);
        return res;
    }
    
    /*
    * 这是我期待的答案
    * 3 3 4 7
    * */
    public  static List<Integer> findClosestElements2(int[] arr, int k, int x) {
        List<Integer> list = Arrays.stream(arr).boxed().collect(Collectors.toList());
        if (x <= arr[0]) return list.subList(0, k);
        int n = arr.length;
        if (x >= arr[n - 1]) return list.subList(n - k, n);
        int idx = Arrays.binarySearch(arr, x);
        if (idx < 0) idx = -idx - 1;
        // 由于 idx 可能返回一个不存在的位置所以，应该是 idx - k，往前数 k 个；右边的话，数 k - 1 个就够了
        int l = Math.max(0, idx - k), r = Math.min(arr.length - 1, idx + k - 1);
        while (r - l > k - 1) {
            if (x - arr[l] <= arr[r] - x) r--;
            else l++;
        }
        return list.subList(l, r + 1);
    }
    
    /*
    * public class Solution {
 	public List<Integer> findClosestElements(int[] arr, int k, int x) {
        List<Integer> ret = Arrays.stream(arr).boxed().collect(Collectors.toList());
		int n = ret.size();
		if (x <= ret.get(0)) {
			return ret.subList(0, k);
		} else if (ret.get(n - 1) <= x) {
			return ret.subList(n - k, n);
		} else {
			int index = Collections.binarySearch(ret, x);
			if (index < 0)
				index = -index - 1;
			int low = Math.max(0, index - k - 1), high = Math.min(ret.size() - 1, index + k - 1);

			while (high - low > k - 1) {
				if ((x - ret.get(low)) <= (ret.get(high) - x))
					high--;
				else if ((x - ret.get(low)) > (ret.get(high) - x))
					low++;
				else
					System.out.println("unhandled case: " + low + " " + high);
			}
			return ret.subList(low, high + 1);
		}
	}
}
    * */
}
